#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define BLOCK_SIZE 3
#define MAX_STACK 200
#define MAX_TRIES 1000000

#define MAP_SIZE (BLOCK_SIZE * BLOCK_SIZE)
#define MAP_BYTES (MAP_SIZE * MAP_SIZE * sizeof(int))

struct record
{
    int map[MAP_SIZE][MAP_SIZE];
    int possible_number[MAP_SIZE][MAP_SIZE];
    int possible_number_count[MAP_SIZE][MAP_SIZE];
};

void print_map(const int (* map)[MAP_SIZE])
{
    for (int i = 0; i < MAP_SIZE; i++)
    {
        for (int j = 0; j < MAP_SIZE; j++)
        {
            if (map[i][j])
                printf("%d ", map[i][j]);
            else
                printf("  ");
            if ((j + 1) % BLOCK_SIZE == 0 && (j + 1) != MAP_SIZE)
                printf("| ");
        }
        putchar('\n');
        if ((i + 1) % BLOCK_SIZE == 0 && (i + 1) != MAP_SIZE)
        {
            for (int j = 0; j < (MAP_SIZE + BLOCK_SIZE - 1) * 2 - 1; j++)
                putchar('-');
            putchar('\n');
        }
    }
}

int init_possible_number(struct record * record)
{
    for (int i = 0; i < MAP_SIZE; i++)
    {
        for (int j = 0; j < MAP_SIZE; j++)
        {
            if (record->map[i][j] > 0) continue;
            int impossible = 0;
            int block_row = i / BLOCK_SIZE * BLOCK_SIZE, block_col = j / BLOCK_SIZE * BLOCK_SIZE;
            for (int k = 0; k < MAP_SIZE; k++)
            {
                // row
                if (record->map[i][k] > 0)
                    impossible |= (1 << record->map[i][k]);
                // column
                if (record->map[k][j] > 0)
                    impossible |= (1 << record->map[k][j]);
                // block
                int row = block_row + k / BLOCK_SIZE, col = block_col + k % BLOCK_SIZE;
                if (record->map[row][col] > 0)
                    impossible |= (1 << record->map[row][col]);
            }
            record->possible_number[i][j] = ~impossible;
            record->possible_number_count[i][j] = 0;
            for (int k = 1; k <= MAP_SIZE; k++)
                if (record->possible_number[i][j] & (1 << k))
                    record->possible_number_count[i][j]++;
            if (record->possible_number_count[i][j] == 0)
                return 0;
        }
    }
    return 1;
}

void get_next_pos(const struct record * record, int * row, int * col, int * finished, int * invalid)
{
    *invalid = 0;
    *finished = 0;
    int min = MAP_SIZE + 1;
    for (int i = 0; i < MAP_SIZE; i++)
        for (int j = 0; j < MAP_SIZE; j++)
        {
            if (record->map[i][j] > 0) continue;
            if (record->possible_number_count[i][j] == 0)
            {
                *invalid = 1;
                return;
            }
            if (record->possible_number_count[i][j] < min)
            {
                *row = i;
                *col = j;
                min = record->possible_number_count[i][j];
            }
        }
    if (min == MAP_SIZE + 1) *finished = 1;
}

void place_number(struct record * record, int row, int col, int number)
{
    record->map[row][col] = number;
    int mask = 1 << number;
    int block_row = row / BLOCK_SIZE * BLOCK_SIZE, block_col = col / BLOCK_SIZE * BLOCK_SIZE;
    for (int i = 0; i < MAP_SIZE; i++)
    {
        // row
        if (record->map[row][i] == 0 && record->possible_number[row][i] & mask) {
            record->possible_number[row][i] &= ~mask;
            record->possible_number_count[row][i]--;
        }
        // column
        if (record->map[i][col] == 0 && record->possible_number[i][col] & mask) {
            record->possible_number[i][col] &= ~mask;
            record->possible_number_count[i][col]--;
        }
        // block
        int r = block_row + i / BLOCK_SIZE, c = block_col + i % BLOCK_SIZE;
        if (record->map[r][c] == 0 && record->possible_number[r][c] & mask) {
            record->possible_number[r][c] &= ~mask;
            record->possible_number_count[r][c]--;
        }
    }
}

int solve(const int (* map)[MAP_SIZE], int (* solution)[MAP_SIZE], int * tries, int * ambiguous)
{
    static struct record stack[MAX_STACK];

    memcpy(stack[0].map, map, MAP_BYTES);

    if (tries) *tries = 0;
    if (ambiguous) *ambiguous = 0;

    if (!init_possible_number(&stack[0]))
        return 0;

    int stack_top = 0;
    int solved = 0;
    int try_count = 0;
    while (stack_top >= 0)
    {
        struct record * current = &stack[stack_top];

        int row, col, finished, invalid;
        get_next_pos(current, &row, &col, &finished, &invalid);

        if (finished)
        {
            if (solution)
                memcpy(solution, current->map, MAP_BYTES);
            if (ambiguous)
            {
                if (solved)
                {
                    *ambiguous = 1;
                    break;
                }
                else
                {
                    stack_top--;
                    solved = 1;
                    continue;
                }
            }
            else
            {
                solved = 1;
                break;
            }
        }

        if (invalid)
        {
            stack_top--;
            continue;
        }

        int first_possible_number = 0;
        int possible = current->possible_number[row][col];
        for (int i = 1; i <= MAP_SIZE; i++)
            if (possible & (1 << i))
            {
                if (first_possible_number == 0)
                    first_possible_number = i;
                else
                {
                    stack_top++;
                    if (stack_top >= MAX_STACK)
                    {
                        printf("Out of memory (stack_top >= %d)\n", MAX_STACK);
                        exit(1);
                    }
                    stack[stack_top] = *current;
                    place_number(&stack[stack_top], row, col, i);
                }
            }
        place_number(current, row, col, first_possible_number);

        try_count++;

        if (try_count >= MAX_TRIES)
        {
            printf("Trying too many times (try_count >= %d)\n", MAX_TRIES);
            exit(1);
        }
    }

    if (tries) *tries = try_count;

    return solved;
}

void generate(int seed, int (* puzzle)[MAP_SIZE])
{
    static struct record stack[MAP_SIZE * MAP_SIZE];

    int stack_top = 0;

    memset(stack[0].map, 0, MAP_BYTES);
    memset(stack[0].possible_number, -1, MAP_BYTES);
    for (int i = 0; i < MAP_SIZE * MAP_SIZE; i++)
        ((int *)stack[0].possible_number_count)[i] = MAP_SIZE;

    srand(seed);

    int ambiguous = 1;
    while (ambiguous)
    {
        struct record * current = &stack[stack_top];

        int pos = rand() % (MAP_SIZE * MAP_SIZE - stack_top);
        for (int i = 0; i <= pos; i++)
            if (((int *)current->map)[i] > 0)
                pos++;
        int pos_row = pos / MAP_SIZE;
        int pos_col = pos % MAP_SIZE;

        int possible = current->possible_number[pos_row][pos_col];
        int number = rand() % current->possible_number_count[pos_row][pos_col] + 1;
        for (int i = 1; i <= number; i++)
            if (!(possible & (1 << i)))
                number++;

        stack_top++;
        stack[stack_top] = *current;
        place_number(&stack[stack_top], pos_row, pos_col, number);

        if (!solve(stack[stack_top].map, 0, 0, &ambiguous))
        {
            stack_top--;
            current->possible_number[pos_row][pos_col] &= ~(1 << number);
            current->possible_number_count[pos_row][pos_col]--;
        }
    }

    memcpy(puzzle, stack[stack_top].map, MAP_BYTES);
}

int main(void)
{
// #define _ 0
//     const int puzzle[MAP_SIZE][MAP_SIZE] =
//     {
//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },

//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },

//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },
//         { _,_,_, _,_,_, _,_,_ },
//     };
// #undef _
    int puzzle[MAP_SIZE][MAP_SIZE];
    srand(time(0));
    int seed = rand();
    printf("Seed: %d\n\n", seed);
    generate(seed, puzzle);

    int solution[MAP_SIZE][MAP_SIZE];

    print_map(puzzle);
    putchar('\n');

    int tries;

    if (solve(puzzle, solution, &tries, 0))
    {
        printf("Solved (%d tries)\n\n", tries);
        print_map(solution);
    }
    else
    {
        printf("Not solvable (%d tries)\n", tries);
    }

    return 0;
}
